Mukalla có vị trí không xa "Cane" hay "Qana'", điểm giao dịch chính thời cổ đại ở Hadrami giữa Ấn Độ và châu Phi, với những khu vực sản xuất hương bên trong nội địa.[2]

Làng chài Mukalla được thành lập vào năm 1035. Khu vực này thuộc quyền quản lý của Oman cho tới giữa thế kỷ 11 rồi mới về với Yemen. Sau khi chứng kiến cuộc tranh giành quyền kiểm soát giữa các nhà nước Hồi giáo Kathiri và Qu'aiti vào thế kỷ 19 và 20, nơi đây trở thành thủ đô của Nhà nước Qu'aiti của Hadhramaut, và sau đó vào năm 1967, trở thành địa phận của Cộng hòa Dân chủ Nhân dân Yemen. Nhà nước Qu'aiti là một phần của Xứ bảo hộ Đông Aden cho tới khi được sáp nhập, với một Cố vấn Anh Quốc lưu trú tại Mukalla. Các thành phố lớn của Nhà nước là Ash-Shihr và Shibam.[1]

Thuyền trưởng Haines, một sĩ quan Anh tới Yemen thăm dò vào thập kỷ 1830, nhận xét Mukalla là một thị trấn có khoảng 4500 cư dân với ngành buôn bán nô lệ phát triển.[3] Vào năm 1934, nhà thám hiểm Anh Freya Stark bắt đầu chuyến đi của bà tới khu vực nội địa Hadhramaut từ Mukalla, và thời gian lưu trú tại thành phố được bà ghi lại trong cuốn The Southern Gates of Arabia.[4]

Nội chiến Yemen

Trong Nội chiến Yemen, vào ngày 2 tháng 4 năm 2015, tổ chức Al-Qaeda tại bán đảo Ả Rập (AQAP) ập vào nhà tù trung ương và phóng thích hàng trăm tù nhân trong đó có hai tư lệnh AQAP kỳ cựu. Họ tấn công ngân hàng trung ương và lấy đi 17 tỉ riyal Yemen cùng 1 triệu đô la Mỹ trước khi nắm quyền kiểm soát dinh tổng thống. Báo chí đưa tin thành phố đã bị Al-Qaeda kiểm soát hoàn toàn và họ dự định thiết lập một tiểu vương quốc Hồi giáo trong vùng Hadramaut.[5] Mukalla trở thành trụ sở của AQAP.

Vào tháng 4 năm 2015 Nasser bin Ali al-Ansi bị tiêu diệt trong một cuộc tấn công của máy bay trinh sát Mỹ theo báo cáo của SITE Intelligence Group.[6]

Vào ngày 3 tháng 11 năm 2015, bão Chapala càn quét thành phố và phá hủy khu vực bờ biển.[7]

Vào ngày 23 tháng 3 diễn ra một cuộc không kích của Mỹ vào trại huấn luyện của AQAP, làm 50 người thiệt mạng. Vài ngày sau AQAP tổ chức một cuộc tụ tập lớn trong thành phố phản đối Hoa Ky.[8] Tháng 4 năm 2016, báo chí đưa tin AQAP bố trí ít nhất 1.000 chiến binh trong thành phố Mukalla, đồng thời tổ chức thu thuế trong thành phố, đem về 2 triệu cho tới trên 5 triệu đô la Mỹ một ngày.[9]

Giành lại Al Qaeda

Mukalla được giành lại từ tay Al Qaeda vào ngày 25 tháng 4 năm 2016 sau khi Quân đội Các Tiểu vương quốc Ả Rập Thống nhất dẫn đầu một cuộc tấn công vào Hội đồng Chuyển tiếp Phía nam và đẩy lùi nhóm này khỏi thành phố.[10]

Các Tiểu vương quốc Ả Rập Thống nhất thành lập ở đây một căn cứ chỉ huy chống AQAP trong thành phố vừa được giải phóng.[11] Căn cứ này giúp CIA và Joint Special Operations Command (JSOC) dễ dàng xác định các cơ sở mạnh nhất của AQAP ở Yemen và tăng cường hợp tác UAE-Hoa Kỳ.[11]

Vào ngày 15 tháng 5 năm 2016, một cuộc tấn công tự sát diễn ra trong thành phố do Nhà nước Hồi giáo Iraq và Levant thực hiện.[12] Cuộc tấn công nhắm vào một sở cảnh sát và làm thiệt mạng ít nhất 25 cảnh sát và làm bị thương ít nhất 54 người khác.[13][14]